# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# root=TreeNode(6)
# root.left=TreeNode(2)
# root.right=TreeNode(8)
# root.left.left=TreeNode(0)
# root.left.right=TreeNode(4)
# root.left.right.left=TreeNode(3)
# root.left.right.right=TreeNode(5)
# root.right.left=TreeNode(7)
# root.right.right=TreeNode(9)
# p=TreeNode(2)
# q=TreeNode(4)
root=TreeNode(3)
root.left=TreeNode(1)
root.right=TreeNode(4)
root.left.right=TreeNode(2)
p=TreeNode(2)
q=TreeNode(4)
def lowestCommonAncestor(root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    while (root.val-p.val)*(root.val-q.val)>0:
        #表示root不符合祖先结点的条件
        if p.val<root.val:
            root=root.left
        else:
            root=root.right
    return root
print(lowestCommonAncestor(root,p,q).val)
